package com.leecode.xiehf.page_01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0040 {

    public static void main(String[] args) {
        Solution_0040 solution = new Solution_0040();
        int[] n = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> s = solution.combinationSum2(n, 8);
        s.forEach(ss -> {
            ss.forEach(sss -> {
                System.out.print(sss + ",");
            });
            System.out.println();
        });
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list = new ArrayList<>();
        combine(candidates, list, new ArrayList<>(), 0, target);
        return list;
    }

    public void combine(int[] nums, List<List<Integer>> list, List<Integer> preList, int index, int target) {
        if (target == 0) {
            list.add(new ArrayList<>(preList));
            return;
        }
        for (int i = index; i < nums.length; i++) {
            int num = nums[i];
            if (num > target) {
                return;
            }
            if (i > index) {
                if (nums[i] == nums[i - 1]) {
                    continue;
                }
            }
            preList.add(num);
            combine(nums, list, preList, i + 1, target - num);
            preList.remove(preList.size() - 1);
        }
    }
}
